import java.util.ArrayList;
import java.util.List;

public class demo2 {
    //注意递归出口的条件，和能添加（的条件和能添加)的条件
    int left=0;
    int right=0;
    int sum=0;
    StringBuilder str;
    List<String> list=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        sum=n;
        str=new StringBuilder();
        dfs();
        return list;
    }
    public void dfs(){
        //当右括号数量等于n时答案符合要求
        if(right==sum){
            list.add(str.toString());
            return;
        }
        if(left<sum){
            str.append('(');
            left++;
            dfs();
            str.setLength(str.length()-1);
            left--;

        }
        if(right<left)
        {
            str.append(')');
            right++;
            dfs();
            str.setLength(str.length()-1);
            right--;
        }
    }
}
